package com.leetcodehot.problems;

public class problems2397 {
    private int m;
    private int n;
    private int[] selectCol;
    private int res;

    public int maximumRows(int[][] matrix, int numSelect) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        selectCol = new int[n];
        dfs(matrix, 0, numSelect);
        return res;
    }

    private void recordRes(int[][] matrix) {
        int count = m;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && selectCol[j] == 0) {
                    count--;
                    break;
                }
            }
        }
        res = Math.max(res, count);
    }

    private void dfs(int[][] matrix, int i, int numSelect) {
        if (i == n) {
            //记录
            recordRes(matrix);
            return;
        }
        //不选
        dfs(matrix, i + 1, numSelect);

        //选
        if (numSelect > 0) {
            selectCol[i]++;
            dfs(matrix, i + 1, numSelect - 1);
            selectCol[i]--;
        }
    }
}
